LeetCode 581. Shortest Unsorted Continuous Subarray

581. Shortest Unsorted Continuous Subarray（最短无序连续子数组）

链接

https://leetcode-cn.com/problems/shortest-unsorted-continuous-subarray

题目

给定一个整数数组，你需要寻找一个连续的子数组，如果对这个子数组进行升序排序，那么整个数组都会变为升序排序。

你找到的子数组应是最短的，请输出它的长度。

示例 1:

输入: [2, 6, 4, 8, 10, 9, 15]
输出: 5
解释: 你只需要对 [6, 4, 8, 10, 9] 进行升序排序，那么整个表都会变为升序排序。
说明 :

输入的数组长度范围在 [1, 10,000]。
输入的数组可能包含重复元素 ，所以升序的意思是<=。

思路

这题方法多种，可以排序之后对比，也可以用别的方法。
首先遍历，由前往后由后往前，分别确定两个边界。前向后时寻找右边界，每个数字判断是否小于前方最大值，若小于，就代表这个数需要排序，若大于，就代表这个数可以放在当前位置，若最后全为升序排列那就不用排序，后向前同理。
以输入示范，首先max为2，之后往后遍历，6>2,max=6,4<6,需要排序，一直往后，right=5，15大于前方所有数字，无需排序。反向遍历，2小于后方所有数，left=1，5-1+1=5.

代码

public int findUnsortedSubarray(int[] nums) {
  int len = nums.length;
  int max = nums[0];
  int min = nums[len - 1];
  int left = 0, right = -1;
  for (int i = 0; i < len; i++) {
    if (max > nums[i]) {
      right = i;
    } else {
      max = nums[i];
    }
  }
  for (int i = len - 1; i > -1; i--) {
    if (min < nums[i]) {
      left = i;
    } else {
      min = nums[i];
    }
  }
  return right - left + 1;
}